package com.up.interview.dataStructuresAndAlgorithms;

/**
 * @author: liuchengjun
 * @title: TwoPointersAlgorithm
 * @projectName: 海联技术中台V2.0
 * @depart 软件事业部
 * @description:
 * @date: 2025/10/23/周四 14:29 (星期四)
 * @since V2.0
 */

import java.util.*;

/**
 * 双指针算法详解
 *
 * 核心思想：使用两个指针在数组/链表中移动，降低时间复杂度
 * 应用场景：从线行数据结构中找出子集，该子集需要满足某种限制（可以不连续）
 *
 * 三大类型：
 * 1. 对撞指针：左右指针相向而行
 * 2. 快慢指针：两个指针同向不同速
 * 3. 滑动窗口：维护一个区间
 */
public class TwoPointersAlgorithm {

    // ==================== 类型1：对撞指针 ====================

    /**
     * 【经典题1】两数之和 II - 有序数组
     * 给定一个已排序的数组，找出两个数使得它们相加之和等于目标数
     * - 小与目标数则移动左指针，反之相反
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     * <p>
     * 使用场景：
     * - 有序数组查找
     * - 三数之和、四数之和
     * - 判断回文串
     */
    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];

            if (sum == target) {
                return new int[]{left + 1, right + 1}; // 返回索引+1
            } else if (sum < target) {
                left++; // 和太小，左指针右移
            } else {
                right--; // 和太大，右指针左移
            }
        }

        return new int[]{-1, -1}; // 没找到
    }

    /**
     * 三数之和 - 标准解法
     * - 对数组进行排序
     * - 固定第一个数，转为两数之和 = -nums[i]   优化点：去除重复元素  -1 -1 -1  第一个-1已经处理，后续-1无需处理  nums[i] == nums[i - 1]时结束当前循环
     * - 两数之和       优化点：去除重复元素  -1  -1  -1  -1 2 2 2 2
     * - -   第一次找到目标数 0 1 7     正常移动左右指针会重复记录
     * - -   将-1移动至最后一个-1      2移动至第一个2  再正常移动
     *
     * 时间复杂度: O(n²)
     * - 排序: O(n log n)
     * - 外层循环: O(n)
     * - 内层双指针: O(n)
     * - 总共: O(n log n) + O(n²) = O(n²)
     *
     * 空间复杂度: O(1) (不算结果集)
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        // 边界判断
        if (nums == null || nums.length < 3) {
            return result;
        }

        // 步骤1: 排序（关键！）
        Arrays.sort(nums);

        // 步骤2: 固定第一个数
        for (int i = 0; i < nums.length - 2; i++) {
            // 优化1: 如果第一个数已经大于0，后面不可能有和为0的三元组
            if (nums[i] > 0) {
                break;
            }

            // 优化2: 跳过重复的第一个数
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 步骤3: 对剩余部分使用双指针（两数之和）
            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i]; // 需要找到两个数的和等于 -nums[i]

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == target) {
                    // 找到一组解
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 跳过重复的left
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 跳过重复的right
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 移动指针
                    left++;
                    right--;

                } else if (sum < target) {
                    // 和太小，左指针右移
                    left++;
                } else {
                    // 和太大，右指针左移
                    right--;
                }
            }
        }

        return result;
    }


    /**
     * 【经典题2】反转字符串
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;

        while (left < right) {
            // 交换左右指针的字符
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }

    /**
     * 【经典题3】判断回文串
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // 跳过非字母数字字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            // 比较字符（忽略大小写）
            if (Character.toLowerCase(s.charAt(left)) !=
                    Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }

    /**
     * 【经典题4】盛水最多的容器
     * 给定n个非负整数，每个代表坐标中的一个点(i, ai)
     * 找出两条线，使得它们与x轴共同构成的容器可以容纳最多的水
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     * <p>
     * 贪心策略：移动较短的那条边
     */
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            // 计算当前面积
            int h = Math.min(height[left], height[right]);
            int width = right - left;
            int area = h * width;
            maxArea = Math.max(maxArea, area);

            // 移动较短的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }

    // ==================== 类型2：快慢指针 ====================

    /**
     * 【经典题5】链表中环的检测
     *    - 判断是否存在环，快慢指针  一个走一步，一个走两步
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     * <p>
     * 使用场景：
     * - 检测链表环
     * - 找链表中点
     * - 找链表倒数第k个节点
     */
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head; // 慢指针，每次走1步
        ListNode fast = head; // 快指针，每次走2步

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // 快慢指针相遇，说明有环
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }

    /**
     * 【经典题6】找链表的中点
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // 当fast到达末尾时，slow正好在中间
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    /**
     * 【经典题7】删除链表倒数第N个节点
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;

        // fast先走n+1步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 然后slow和fast一起走，直到fast到末尾
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 删除slow的下一个节点
        slow.next = slow.next.next;

        return dummy.next;
    }

    /**
     * 【经典题8】移除数组中的元素（原地修改）
     * 给你一个数组和一个值val，原地移除所有等于val的元素
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     * <p>
     * 使用场景：
     * - 原地删除/去重
     * - 数组分区
     */
    public static int removeElement(int[] nums, int val) {
        int slow = 0; // 慢指针：指向下一个要填入的位置

        for (int fast = 0; fast < nums.length; fast++) {
            // 快指针遍历数组
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }

        return slow; // 返回新数组长度
    }

    /**
     * 【经典题9】删除有序数组中的重复项
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int slow = 0; // 慢指针：指向不重复元素的末尾

        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }

        return slow + 1;
    }

    // ==================== 类型3：滑动窗口 ====================

    /**
     * 滑动窗口
     * -      * 【关键性质】单调性
     *      * 如果 [left, right] 包含重复字符，
     *      * 那么所有 [left, right+1], [left, right+2]... 也一定包含重复字符  所以移动left确保当前区间不重复
     *
     *
     * 【经典题10】最长无重复子串
     * 给定一个字符串，找出不含有重复字符的最长子串的长度
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(min(n,m))，m是字符集大小
     * <p>
     * 使用场景：
     * - 子串/子数组问题
     * - 固定/可变长度窗口
     * - 字符串匹配
     */
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // 如果窗口中有重复字符，收缩左边界
            while (window.contains(c)) {
                window.remove(s.charAt(left));
                left++;
            }

            // 加入当前字符
            window.add(c);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }

    /**
     * 【经典题11】最小覆盖子串
     * 给定字符串s和t，找出s中包含t所有字符的最小子串
     * <p>
     * 时间复杂度: O(|s| + |t|)
     * 空间复杂度: O(|t|)
     */
    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        // 统计t中每个字符的频率
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int valid = 0; // 窗口中满足need条件的字符个数

        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            // 扩大窗口
            char c = s.charAt(right);
            right++;

            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 收缩窗口
            while (valid == need.size()) {
                // 更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left);
                left++;

                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    /**
     * 【经典题12】固定长度的最大和子数组
     * 给定数组和整数k，找出长度为k的子数组的最大和
     * <p>
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static int maxSumSubarray(int[] nums, int k) {
        int windowSum = 0;

        // 计算第一个窗口的和
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        int maxSum = windowSum;

        // 滑动窗口
        for (int i = k; i < nums.length; i++) {
            windowSum = windowSum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    // ==================== 测试代码 ====================

    public static void main(String[] args) {
        System.out.println("========== 对撞指针测试 ==========");

        // 两数之和
        int[] nums1 = {2, 7, 11, 15};
        int[] result1 = twoSum(nums1, 9);
        System.out.println("两数之和: [" + result1[0] + ", " + result1[1] + "]");

        // 反转字符串
        char[] s = {'h', 'e', 'l', 'l', 'o'};
        reverseString(s);
        System.out.println("反转字符串: " + new String(s));

        // 判断回文
        System.out.println("是否回文: " + isPalindrome("A man, a plan, a canal: Panama"));

        // 盛水容器
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("最大盛水量: " + maxArea(height));

        System.out.println("\n========== 快慢指针测试 ==========");

        // 创建链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode middle = findMiddle(head);
        System.out.println("链表中点: " + middle.val);

        // 删除重复元素
        int[] nums2 = {1, 1, 2, 2, 3, 4, 4};
        int newLen = removeDuplicates(nums2);
        System.out.print("去重后: ");
        for (int i = 0; i < newLen; i++) {
            System.out.print(nums2[i] + " ");
        }
        System.out.println();

        System.out.println("\n========== 滑动窗口测试 ==========");

        // 最长无重复子串
        String s1 = "abcabcbb";
        System.out.println("最长无重复子串长度: " + lengthOfLongestSubstring(s1));

        // 最小覆盖子串
        String s2 = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println("最小覆盖子串: " + minWindow(s2, t));

        // 固定长度最大和
        int[] nums3 = {2, 1, 5, 1, 3, 2};
        System.out.println("长度为3的最大和: " + maxSumSubarray(nums3, 3));
    }
}
